package com.chenyi.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * [70]爬楼梯
 *
 * @author by chenyi
 * @className ClimbingStairs
 * @date 2022-06-23 22:55:09
 */
public class ClimbingStairs {
    public static void main(String[] args) {
        Solution solution = new ClimbingStairs().new Solution();
        System.out.println(solution.climbStairs2(8));
    }

    @SuppressWarnings("AlibabaCommentsMustBeJavadocFormat")
            //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 暴力递归解法
         *
         * @param n
         * @return
         */
        public int climbStairs(int n) {
            if (n == 1) {
                return 1;
            }
            if (n == 2) {
                return 2;
            }
            return climbStairs(n - 1) + climbStairs(n - 2);
        }

        /**
         * 动态规划，自底向上解法
         * @param n
         * @return
         */
        public int climbStairs1(int n) {
            if (n == 1) {
                return 1;
            }
            if (n == 2) {
                return 2;
            }
            // 跳一层和跳二层为已知解可以显示保存
            int a = 1;
            int b = 2;
            int temp = 0;
            for (int i = 3; i <= n; i++) {
                // 计算上一层的使用解法，公式： f(n) = f(n - 1) + f(n - 2)
                temp = a + b;
                // 动态规划核心保存已经计算过的值，如果b为第4层的次数那么赋值给a，temp同理
                a = b;
                b = temp;
            }
            return temp;
        }

        /**
         * 记忆递归需要存储已经计算过的值
         */
        private Map<Integer, Integer> map = new HashMap<>();

        /**
         * 记忆递归，自顶向下
         * @param n
         * @return
         */
        public int climbStairs2(int n) {
            if (n == 1) {
                return 1;
            }
            if (n == 2) {
                return 2;
            }
            // 判断当前位置是否计算过
            if (map.containsKey(n)) {
                return map.get(n);
            }
            // 如果没有计算过那么递归调用进行计算
            map.put(n, (climbStairs2(n - 1) + climbStairs2(n - 2)));
            return map.get(n);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
